/*
day170
2020.2.14
*/
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;

class Solution1 {
public:
    int integerBreak(int n) {
        int *arr=(int *)malloc(sizeof(int)*(n+1));
        arr[0]=arr[1]=arr[2]=1;
        for(int i=3;i<n+1;++i)
        {
        	arr[i]=i-1;
        	for(int j=1;i-j>=1;++j)
        	{
        		int tem1=arr[i-j]>(i-j) ? arr[i-j] : (i-j);
        		int tem2=tem1*j;
        		arr[i]=arr[i]>tem2 ? arr[i] : tem2;
			}
		}
//		for(int i=1;i<=n;++i)
//		{
//			cout<<"arr["<<i<<"]="<<arr[i]<<endl;
//		}cout<<endl;
		return arr[n];
    }
};

/*

*/ 
class Solution2 {
public:
    int integerBreak(int n) {
        if(n<=3)	return n-1;
		int a=n/3;
		int b=n%3;
		if(b==0){return pow(3,a);} 
		if(b==1){return pow(3,a-1)*4;};
		return pow(3,a)*2;
    }
};
int main()
{
	Solution2 s;
	cout<<s.integerBreak(10)<<endl;
	return 0;
}
